package medium

import (
	. "GoLeetcode/common"
	"math"
	"sort"
)

/*
时间复杂度:O(N)
空间复杂度:O(N)

贪心+单调栈

难：如何找到当前元素cur右边大于等于自己且最远的元素
解：首先从左到右遍历nums，以nums[0]作为栈中第一个元素，只有当前遍历的元素cur<nums[0]时才入栈(构建一个以nums[0]开始的单调递减栈)
	然后再从右往左遍历nums，一旦当前元素cur>=栈顶元素则出栈，并计算索引差；在遍历过程中记录最大索引差即可

*/

func maxWidthRamp(nums []int) int {
	stack := make([]int, 0)
	// 构建以nums[0]为第一个元素的单调递减的栈
	for i, v := range nums {
		if len(stack) == 0 || v < nums[stack[len(stack)-1]] {
			stack = append(stack, i)
		}
	}

	ans := 0
	for i := len(nums) - 1; i > 0; i-- {
		for len(stack) > 0 && nums[i] >= nums[stack[len(stack)-1]] {
			pos := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans = Max(ans, i-pos)
		}
	}
	return ans
}

/*
时间复杂度:O(NlogN)
空间复杂度:O(N)

排序+贪心

*/

func maxWidthRamp1(nums []int) int {
	arr := make([][2]int, len(nums))
	for i, v := range nums {
		arr[i] = [2]int{i, v}
	}
	// 根据元素大小排序
	sort.SliceStable(arr, func(i, j int) bool {
		return arr[i][1] < arr[j][1]
	})

	minIdx := math.MaxInt32
	ans := 0
	for _, v := range arr {
		if minIdx > v[0] {
			minIdx = v[0]
		}
		ans = Max(ans, v[0]-minIdx)
	}
	return ans
}
